package cn.im;


import org.junit.Test;

/**
 * 排序算法
 * 
 * @author Kevin
 *
 */
public class Sort {

	private static int[] arrs = { 12, 3, 6, 34, 44, 3, 67, 2 };

	public static void main(String[] args) {

		quickSort(arrs,0,arrs.length-1);

		for (int i : arrs) {
			System.out.print(i + " ");
		}

//		System.out.println(10/2+";"+11/2);
	}

	/**
	 * 交换--冒泡排序
	 * 基本思想：循环遍历多次，每次操作比较相邻的两个元素，每轮确定一个最大元素到最后方
	 * 时间复杂度：O(n^2)
	 */
	@Test
	public void bubbleSort(){
		for (int i=arrs.length-1 ; i >= 0 ; i--){
			for (int j=0 ; j < i ; j++){
				if(arrs[j] > arrs[j+1]){
					swap(arrs,j,j+1);
				}
			}
		}

		for (int i : arrs) {
			System.out.print(i + " ");
		}
	}

	/**
	 * 交换--快速排序
	 * 基本思想：将序列分为两部分：左边小于游标，右边大于游标；使用递归思想重复上述步骤，直至全部排序完成
	 * 时间复杂度：O(nlogn)
	 */
	public static void quickSort(int[] arr,int left ,int right){
		int low = left;
		int high = right;
		if(left >= right) return; //递归终止条件

		int k = arr[low];  //游标，额外空间k

		while (low < high){
			while (low<high && arr[high]>=k ){
				high--;
			}
			arr[low] = arr[high];

			while (low<high && arr[low]<=k){
				low++;
			}
			arr[high] = arr[low];
		}
		arr[low]=k;
		quickSort(arr,left,low-1);
		quickSort(arr,low+1,right);
	}

	/**
	 * 	插入--直接插入排序
	 * 	基本思想：将序列前段看为有序队列，将后段的数据逐个插入到前段有序队列中，完成排序。
	 * 	时间复杂度：O(n^2)
 	 */
	@Test
	public void insertSort(){
		for (int i=1; i<arrs.length; i++){
			for ( int j = i ; j>0 ;j--){
				if(arrs[j] < arrs[j-1]){
					swap(arrs,j,j-1);
				}
			}
		}
		for (int i : arrs) {
			System.out.print(i + " ");
		}
	}

	/**
	 * 插入--希尔排序
	 * 基本思想：考虑有序性，先分若干组分别计算
	 */
	public void shellsort (int a[])
	{
		int d=a.length;
		int team=0;//临时变量
		for(;d>=1;d/=2)//共分成d组
			for(int i=d;i<a.length;i++)//到那个元素就看这个元素在的那个组即可
			{
				team=a[i];
				for(int j=i-d;j>=0;j-=d)
				{
					if(a[j]>team)
					{
						a[j+d]=a[j];
						a[j]=team;
					}
					else {
						break;
					}
				}
			}
	}


	/**
	 * 选择排序
	 * 基本思想：从第一位开始，从右侧选择最小的数值放到左侧
	 */
	public  void selectionSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[i] > arr[j]) {
					swap(arr, j, i);
				}
			}
		}
	}

	/**
	 * 根据下标，交换数组中的两个数值
	 * 
	 * @param arr
	 * @param a
	 * @param b
	 */
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}
